package leetcode;
/**
 * 剑指Offer 51.数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * 输入: [7,5,6,4]
 * 输出: 5
 * 0 <= 数组长度 <= 50000
 */
public class Offer_51 {
    //利用归并排序
    public int reversePairs(int[] nums) {
        //考虑数组长度
        if(nums.length <= 1){
            return 0;
        }
        return mergeSortInternal(nums, 0, nums.length - 1);
    }
    //求[l, r]区间内的逆序对个数
    private int mergeSortInternal(int[] nums, int l, int r) {
        //边界条件
        if(l >= r){
            //子数组只剩下一个元素
            return 0;
        }
        int mid = l + (r - l) / 2;
        int left = mergeSortInternal(nums, l, mid);
        int right = mergeSortInternal(nums, mid + 1, r);
        if(nums[mid] <= nums[mid + 1]){
            return left + right;
        }else{
            return left + right + merge(nums, l, mid, r);
        }
    }
    //将[l, r]区间内的元素进行排序，并返回区间内的逆序对
    private int merge(int[] nums, int l, int mid, int r) {
        //建立临时数组，存储[l, r]的元素
        int[] temp = new int[r - l + 1];
        for(int i = 0; i < temp.length; i++){
            temp[i] = nums[l + i];
        }
        int i1 = 0, i1End = mid - l, i2 = mid - l + 1, count = 0;
        //同时遍历两条子数组，并修改区间元素顺序
        for(int k = l; k <= r; k++){
            if(i1 == i1End + 1){
                //第一条数组完毕，直接添加第二条数组元素
                nums[k] = temp[i2];
                i2 ++;
            }else if(i2 == r - l + 1){
                //第二条数组完毕，直接添加第一条数组元素
                nums[k] = temp[i1];
                i1 ++;
            }else if(temp[i1] <= temp[i2]){
                nums[k] = temp[i1];
                i1 ++;
            }else{
                //此时temp[i1] > temp[i2]
                nums[k] = temp[i2];
                i2 ++;
                //则对于[i1, i1End]区间内的所有元素都可以和i2匹配逆序对
                count += i1End - i1 + 1;
            }
        }
        return count;
    }
}
